#include<iostream>
#include<deque>  //用于存储指向上一位置节点指针和输出的容器
using namespace std;
struct Node
{
	int x;
	int y;
	Node* prev;  //进队列需要
	Node* next;  //出队列需要
};
class Queue {
private:
	Node* head;
	Node* tail;
	int length;
public:
	Queue();
	~Queue();
	void pushQueue(int x, int y);
	pair<int, int>popQueue();
	bool is_emptyQueue();
};
bool Queue::is_emptyQueue() {
	return this->length == 0;
}
pair<int, int> Queue::popQueue() {
	if (this->length == 0)return make_pair(-1, -1);
	Node* p = this->head->next;
	this->head->next = p->next;
	this->length--;
	int x = p->x; int y = p->y;
	delete p;
	return make_pair(x, y);
}
void Queue::pushQueue(int x, int y) {
	Node* p = new Node;
	p->next = nullptr; p->prev = this->tail;
	this->tail->x = x; this->tail->y = y; this->tail->next = p; this->tail = p;
	this->length++;
}
Queue::~Queue() {
	Node* p = this->head;
	while (this->head!=nullptr)
	{
		this->head = this->head->next;
		delete p;
		p = this->head;
	}
}
Queue::Queue() {
	this->head = new Node;
	this->tail = new Node;
	this->head->prev = this->tail->next = nullptr;
	this->head->next = this->tail;
	this->tail->prev = this->head;
	this->length = 0;
}
void destoryPath(deque<Node*>& de) {  //暂时没有好方案释放函数enterPath的static静态空间，废弃
	Node* temp = nullptr;
	for (deque<Node*>::iterator it = de.begin(); it != de.end(); it++) {
		delete* it;//由于所有节点都在容器中，所以从头到尾删除就行
	}
}
bool enterPath(int x, int y, int next_x, int next_y, Queue& queue, int maze[][10], bool getValue=false) {
	static Node* source = new Node;  //存放起始位置节点，所有路径的源头，便于vPath找由此衍生出的最新路径
	static deque<Node*>vPath;   //存放指向路径树新旧节点的指针
	static bool is_inited = false;  //是否初始化标志
	if (getValue) {  //打印标志，路径查找完毕之后打印标志为true，进入打印流程，默认为false
		deque<pair<int, int>>result; int count = 0; //结果存放容器和计数器
		for (deque<Node*>::iterator it = vPath.begin(); it != vPath.end(); it++) {
			if ((*it)->x == 8 && (*it)->y == 8) {  //由于最新节点指针都是从头开始插入，故从前往后遍历更合适
				Node* p = *it;  //此时*it指向路径最后一个节点，即最后加入的<8，8>
				while (p!=nullptr)
				{
					result.push_front(make_pair(p->x, p->y));  //添加节点进入路径容器
					p = p->prev;  //找路径上一位置，循环添加直到<1,1>
				}
				break;  //找到了就没必要循环了
			}
		}
		destoryPath(vPath);
		for (deque<pair<int, int>>::iterator it = result.begin(); it != result.end(); it++) {
			cout << "<" << (*it).first << "," << (*it).second << ">" << "\t"; count++;
			if (count % 10 == 0)cout << endl;
		}return true;//此时直接返回就可
	}
	if (!is_inited) { //首次进入该函数未初始化static数据时进入判断，后续不会进入
		source->x = 1; source->y = 1; source->next = nullptr; source->prev = nullptr;  //便于后续操作统一
		vPath.push_front(source);  //将源点加入路径可能路径数组中，避免特殊化操作
		is_inited = true;  //初始化完毕，将初始化标志解除
	}
	for (deque<Node*>::iterator it = vPath.begin(); it != vPath.end(); it++) {
		if ((*it)->x == x && (*it)->y == y) {  //找到此时新地点的前一节点，开始延申路线
			Node* p = new Node;
			p->x = next_x; p->y = next_y; p->prev = (*it); p->next = nullptr;  //新节点初始化
			vPath.push_front(p);  //路线加入队列，新元素必然更靠近出口，头插法本函数循环次数就会低很多
			if (next_x == 8 && next_y == 8)return true;  //找到了出口，此时返回true引发连锁反应迅速结束递归
			queue.pushQueue(next_x, next_y); //还没找到就把最新位置入队
			maze[next_x][next_y] = -1; //走过了就不在考虑了
			break; //找到了就不用循环了
		}
	}
	return false;
}
bool tryThisStep(int x, int y, int maze[][10], Queue& queue) {
	for (int i = 0; i < 4; i++) {
		switch (i)
		{
		case 0: {if (maze[x - 1][y] == 0) { if (enterPath(x, y, x - 1, y, queue, maze))return true; }}break;
		case 1: {if (maze[x][y + 1] == 0) { if (enterPath(x, y, x, y + 1, queue, maze))return true; }}break;
		case 2: {if (maze[x + 1][y] == 0) { if (enterPath(x, y, x + 1, y, queue, maze))return true; }}break;
		case 3: {if (maze[x][y - 1] == 0) { if (enterPath(x, y, x, y - 1, queue, maze))return true; }}break;
		default:// 不断判断当前位置上下左右，不断尝试，一旦调用函数返回true即返回true，连锁结束solve函数
			break;
		}
	}
	return false;//还没找到，那就继续
}
bool solve(Queue& queue,int maze[][10]) {
	if (queue.is_emptyQueue())return false;  //空队列说明没有还未涉足的路线地点了，还在调用自身说明无解了
	auto obj = queue.popQueue(); //取出一个最新位置，交给tryThisStep函数尝试解题
	int x = obj.first; int y = obj.second;
	if (tryThisStep(x, y, maze, queue))return true; //调用函数发现了也就没必要找了，直接返回
	return solve(queue, maze);  //这一轮找不到，下一轮，把下一轮结果返回，终归找得到true或者无解返回flase
}
void test() {
	int maze[10][10] = {
		{1,1,1,1,1,1,1,1,1,1},{1,0,0,1,0,0,0,1,0,1},
		{1,0,0,1,0,0,0,1,0,1},{1,0,0,0,0,1,1,0,0,1},
		{1,0,1,1,1,0,0,0,0,1},{1,0,0,0,1,0,0,0,0,1},
		{1,0,1,0,0,0,1,0,0,1},{1,0,1,1,1,0,1,1,0,1},
		{1,1,0,0,0,0,0,0,0,1},{1,1,1,1,1,1,1,1,1,1}, };
	Queue queue; queue.pushQueue(1, 1); maze[1][1] = -1;
	if (solve(queue, maze))enterPath(8, 8, 8, 8, queue, maze, true);//返回true说明找到，打印
}
int main() {
	test();
	return 0;
}